/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  console.log('hello world');

  let arr = [];

  diff(0, 0, n, '');
  console.log(arr);

  /**
   *
   * @param {number} left
   * @param {number} right
   * @param {number} n
   * @param {string} str
   */
  function diff(left, right, n, str) {
    // 什么时候应该退出呢？
    if (left + right === n * 2) {
      arr.push(str);
      return;
    }

    // 什么时候应该递归？
    if (left < n) {
      //  n == 3 (( =》 (((
      diff(left + 1, right, n, str + '(');
    }

    if (right < left) {
      //  (() =》 (()) (())( => (())()
      diff(left, right + 1, n, str + ')');
    }
  }
};

generateParenthesis(3);
